package net.lainiao.leetcode;


import net.lainiao.leetcode.base.Common;
import net.lainiao.leetcode.base.TreeNode;

public class LintCode72 {
    //根据中序遍历和后序遍历树构造二叉树
    public static void main(String[] args) {
        int[] mds = {3,4,2,5,6,8,7,9};
        int[] ads = {3,2,4,5,8,9,7,6};
        LintCode72 code = new LintCode72();
        TreeNode root = code.buildTree(mds, ads);
        Common.showJsonForObject(root,true);
//        M: 左->中->右
//        A: 左->右->中
    }

    private int inIndex;
    private int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        inIndex=inorder.length-1;
        postIndex=postorder.length-1;
        return buildTree(inorder,postorder,null);
    }

    public TreeNode buildTree(int[] inOrder,int[] postOrder,TreeNode endNode){
        if(postIndex<0){
            return null;
        }
        TreeNode current=new TreeNode(postOrder[postIndex]);
        postIndex--;

        if(inOrder[inIndex]!=current.val){
            current.right=buildTree(inOrder,postOrder,current);
        }

        inIndex--;
        if(endNode==null||inOrder[inIndex]!=endNode.val){
            current.left=buildTree(inOrder,postOrder,endNode);
        }
        return current;
    }
}
